package recursion.nowcoder.medium;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bruin_du
 * @description 幸运的袋子
 * https://www.nowcoder.com/practice/a5190a7c3ec045ce9273beebdfe029ee?
 * tpId=85&&tqId=29839&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
 * @date 2022/5/11 20:31
 **/
public class LuckyBags {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextInt();
            }
            //先排序,为了后面好剪枝
            Arrays.sort(arr);
            //使用的深度递归和剪枝操作
            System.out.println(count(arr, n, 0, 0, 1));
        }
    }

    //每层的情况都可以看作每次递归在数组上的操作
    //每层数组都有都有自己的偏移量
    private static int count(int[] arr, int n, int pos, int sum, int mul) {
        //保存后序的递归和本层的袋子数
        int count = 0;
        for (int i = pos; i < n; i++) {
            //先计算和和乘积,好为了后面进行判断
            sum += arr[i];
            mul *= arr[i];
            //如果和大于乘积,说明这是一个可以的方案
            //count + 1并往后递归
            if(sum > mul){
                count += 1 + count(arr,n,i + 1,sum,mul);
            }
            //走到这里,说明和没有大于乘积,但是由于 1 和任意一个数的和都是大于乘积的
            //所以可以往后递归判断一下,但是不加一
            else if(arr[i] == 1){
                count += count(arr,n,i + 1,sum,mul);
            }
            //走到这里说明前面两种情况都是不满足的
            //直接放弃本层的数以及后面的数
            //因为数组经过排序的,当前的数都不满足条件,后面的数都是大等于的当前的数
            //所以直接结束循环,返回count
            else
                break;
            //当有递归返回的时候才能走到这里
            //说明这层的这个以及之前的数已经判断过了,往后判断后面的数的组合情况
            //所以进行回溯,和减去当前的数,乘积除以当前数
            sum -= arr[i];
            mul /= arr[i];
            //这里会跳过当前层数的相同的值,因为相同的值是一样的情况
            //就不需要进行判断了
            while(i < n - 1 && arr[i] == arr[i + 1]){
                i++;
            }
        }
        return count;
    }
}
